package dp;

/**
 * 每次必须走一步的机器人走到一个规定位置的问题，在限制步数的情况下有多少种走法
 *
 * @author Liaorun
 */
public class RobotWalk {

    public static void main(String[] args) {
        System.out.println(walkWays(3, 3, 1, 1));
    }

    /**
     * @param allPosNum 一共是1~n 这么多位置， 固定参数
     * @param aimPos    最终的目标是e, 固定参数
     * @param restStep  还剩rest步需要走
     * @param curPos    当前机器人的位置
     * @return
     */
    public static int walkWays(int allPosNum, int aimPos, int curPos, int restStep) {
        int[][] dp = new int[restStep + 1][allPosNum + 1];


        for (int i = 0; i <= restStep; i++) {
            for (int j = 0; j <= allPosNum; j++) {
                dp[i][j] = -1;
            }
        }

        System.out.println(dp[0][0]);

        return f(allPosNum, aimPos, restStep, curPos, dp);
    }

    /**
     * @param allPosNum 一共是1~n 这么多位置， 固定参数
     * @param aimPos    最终的目标是e, 固定参数
     * @param rest      还剩rest步需要走
     * @param cur       当前机器人的位置
     * @param dp
     * @return 返回的走法数
     */
    private static int f(int allPosNum, int aimPos, int rest, int cur, int[][] dp) {

        // 查询缓存是否已经尝试出答案了
        if (dp[rest][cur] != -1) {
            return dp[rest][cur];
        }
        // base case
        // 还有0次，当前位置为目标位置，即是成功的一个方法
        if (rest == 0) {
            dp[rest][cur] = cur == aimPos ? 1 : 0;
            return cur == aimPos ? 1 : 0;
        }

        // 机器人在左侧，只能向右走，走到2的位置
        if (cur == 1) {
            dp[rest][cur] = f(allPosNum, aimPos, rest - 1, 2, dp);
        } else if (cur == allPosNum) {
            // 机器人在右侧，只能向左走
            dp[rest][cur] = f(allPosNum, aimPos, rest - 1, allPosNum - 1, dp);
        } else {
            // 机器人在中间位置，可以向左走也可以向右走
            dp[rest][cur] = f(allPosNum, aimPos, rest - 1, cur - 1, dp) + f(allPosNum, aimPos, rest - 1, cur + 1, dp);
        }

        return dp[rest][cur];
    }

    /**
     * 严格表结构的动态规划，解决机器人问题
     *
     * @param N 一共是1~n 这么多位置， 固定参数
     * @param P 最终的目标是e, 固定参数
     * @param M 还剩rest步需要走
     * @param K 当前机器人的位置
     * @return
     */
    public static int dpWay(int N, int P, int M, int K) {
        int[][] dp = new int[K + 1][N + 1];
        // base case
        // 第一行只有目标位置算一个方法
        dp[0][P] = 1;

        for (int rest = 1; rest < K; rest++) {
            for (int cur = 0; cur < N; cur++) {
                if (cur == 1) {
                    // 第一列的等于右上角的
                    dp[rest][1] = dp[rest - 1][2];
                } else if (cur == N) {
                    // 最后一列的等于左上角的
                    dp[rest][cur] = dp[rest - 1][N - 1];
                } else {
                    dp[rest][cur] = dp[rest - 1][cur - 1] + dp[rest - 1][cur + 1];
                }
            }
        }

        return dp[M][K];
    }
}
